package com.zxy.javaarithmetic.tree;

import com.zxy.javaarithmetic.Utils;
import com.zxy.javaarithmetic.bean.TreeNode;

import java.util.Stack;

/**
 * @author : Shonn.Zhang
 * @email : shonn.zhang@mart.blue
 * @time : 2021/8/27 15:01
 * @desc : 二叉树的遍历
 */
public class TraverseDemo {

    public static void main(String[] args) {
        TreeNode treeNode = Utils.createBinaryTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});

        System.out.print("preOrder:  ");
        preOrder(treeNode);
        System.out.println();

        System.out.print("preOrder2: ");
        preOrder2(treeNode);
        System.out.println();

        System.out.print("inOrder:   ");
        inOrder(treeNode);
        System.out.println();

        System.out.print("inOrder2:  ");
        inOrder2(treeNode);
        System.out.println();

        System.out.print("postOrder: ");
        postOrder(treeNode);
        System.out.println();

        System.out.print("postOrder2: ");
        postOrder2(treeNode);
        System.out.println();
    }

    /**
     * 前序遍历，递归实现
     *
     * @param root
     */
    private static void preOrder(TreeNode root) {
        if (root == null) return;

        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 前序遍历非递归,借助栈结构
     *
     * @param root
     */
    private static void preOrder2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");

            if (node.right != null) {
                stack.push(node.right);
            }

            if ((node.left != null)) {
                stack.push(node.left);
            }
        }
    }

    /**
     * 中序遍历，递归法
     *
     * @param root
     */
    private static void inOrder(TreeNode root) {
        if (root == null) return;

        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    /**
     * 中序遍历，非递归
     *
     * @param root
     */
    private static void inOrder2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {

            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            if (!stack.isEmpty()) {
                node = stack.pop();
                System.out.print(node.val + " ");
                node = node.right;
            }
        }
    }

    /**
     * 后序遍历，递归法
     * @param root
     */
    private static void postOrder(TreeNode root) {
        if (root == null) return;

        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    /**
     * 后续遍历，非递归，双栈法
     * @param root
     */
    private static void postOrder2(TreeNode root){
        Stack<TreeNode> printStack = new Stack<>();
        Stack<TreeNode> traverseStack = new Stack<>();
        traverseStack.push(root);

        while (!traverseStack.isEmpty()){
            TreeNode node = traverseStack.pop();

            if(node.left != null){
                traverseStack.push(node.left);
            }
            if(node.right != null){
                traverseStack.push(node.right);
            }

            printStack.push(node);
        }

        while (!printStack.isEmpty()){
            System.out.print(printStack.pop().val+" ");
        }
    }
}
